#include <iostream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <vector>
#include <queue>
class Node;
bool cmpNode(Node*, Node*);
class Node {
public:
Node(int number): number(number) {}
void edge(Node* child) {
childs.push_back(child);
std::sort(this->childs.begin(), this->childs.end(), cmpNode);
}
void check(void) {
if(childs.size()==0) {
this->isLeaf=true;
} else {
this->roads=childs.begin();
this->isLeaf=false;
}
}
void nextRoad(void) {
roads++;
if(roads==childs.end()) roads=childs.begin();
}
int getNumber(void) { return this->number; }
int getSum(void) { return this->sum; }
int push(int number) {
if(isLeaf) {
this->sum+=number;
return this->number;
} else {
int value=(*roads)->push(number);
this->nextRoad();
return value;
}
}
private:
std::vector<Node*> childs;
std::vector<Node*>::iterator roads;
int number, sum=0;
bool isLeaf=false;
};
bool cmpNode(Node* n1, Node* n2) {
return n1->getNumber()<n2->getNumber();
}
class Tree {
public:
Tree(int number) {
for(int i=1; i<=number; ++i) {
Node* node=new Node(i);
this->whole.push_back(node);
}
}
~Tree(void) {
for(auto iter=this->whole.begin(); iter!=this->whole.end(); ++iter) delete *iter;
}
void edges(std::vector<std::pair<int, int>> edges) {
for(std::pair<int, int> edge: edges) {
this->whole[edge.first-1]->edge(this->whole[edge.second-1]);
}
for(int i=0; i<this->whole.size(); ++i) whole[i]->check();
}
int push(int number) {
return this->whole[0]->push(number);
}
std::vector<int> getSums(void) {
std::vector<int> sums;
for(int i=0; i<whole.size(); ++i) {
sums.push_back(whole[i]->getSum());
}
return sums;
}
private:
std::vector<Node*> whole;
};
auto findNumber = [](const std::vector<std::pair<int, int>>& edges) {
int number = 0;
for (auto edge : edges) {
if (number < edge.second)
number = edge.second;
}
return number;
};
auto checkFailed = [](const std::vector<int> &target,
const std::vector<int> &sums) {
assert(target.size() == sums.size());
for (int i = 0; i < target.size(); ++i) {
if (target[i] < sums[i])
return false;
}
return true;
};
auto vecSum = [](const std::vector<int> &v) {
return std::accumulate(v.begin(), v.end(), 0);
};
auto coutV = [](const std::vector<int> &v) {
for (int item : v)
std::cout << item << ' ';
std::cout << std::endl;
};
auto sequence = [](const std::vector<std::pair<int, int>> edges, int max) {
Tree tree(findNumber(edges));
tree.edges(edges);
std::vector<int> seq;
for (int i = 0; i < max; ++i)
seq.push_back(tree.push(1));
return seq;
};
auto allNegative = [](const std::vector<int> &vec) {
return all_of(vec.begin(), vec.end(), [](int x) { return x < 1; });
};
auto minimalCount = [](const std::vector<int> &seq,
const std::vector<int> &target) {
int max = seq.size();
std::vector<int> req(target.size(), 0);
for (int i = 0; i < target.size(); ++i) {
int div = target[i] / 3, mod = target[i] % 3;
req[i] = mod != 0 ? div + 1 : div;
}
int count = 0;
for (auto iter = seq.begin(); iter != seq.end(); ++iter, ++count) {
req[*iter - 1]--;
if (allNegative(req))
return count+1;
}
return -1;
};
auto pushValue = [](const int remain, const int remainC) {
if(remain>3*remainC || remain<remainC) return -1;
if((remain-(remainC-1)*3)>0) return remain-(remainC-1)*3;
if(remainC==2) return 1;
return remain%3;
};
auto remainCount = [](int nodeNum, const std::vector<int>& seq, int num) {
std::vector<int> counter(nodeNum, 0);
for (int i = 0; i < num; ++i)
counter[seq[i] - 1]++;
return counter;
};
std::vector<int> solution(std::vector<std::pair<int, int>>& edges, std::vector<int>& target) {
std::vector<int> seq=sequence(edges, vecSum(target));
int requireNum=minimalCount(seq, target);
std::vector<int> result, remainNum=target,
remainC=remainCount(findNumber(edges), seq, requireNum);
for(int i=0; i<requireNum; ++i) {
int value=pushValue(remainNum[seq[i]-1], remainC[seq[i]-1]);
if(value==-1) return std::vector<int>(1, -1);
remainC[seq[i]-1]--;
remainNum[seq[i]-1]-=value;
result.push_back(value);
}
return result;
};
int main(void) {
std::vector<std::pair<int, int>> edges={{1, 3}, {1, 2}};
std::vector<int> target={0, 7, 1};
std::vector<int> result=solution(edges, target);
coutV(result);
return 0;
}